home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / ccs / ccs-11tl.lha / lbl / sun / tifflib / tif_lzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-20  |  23.8 KB  |  950 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/tiff/libtiff/RCS/tif_lzw.c,v 1.37 92/02/12 11:27:28 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1988, 1989, 1990, 1991, 1992 Sam Leffler
  7.  * Copyright (c) 1991, 1992 Silicon Graphics, Inc.
  8.  *
  9.  * Permission to use, copy, modify, distribute, and sell this software and 
  10.  * its documentation for any purpose is hereby granted without fee, provided
  11.  * that (i) the above copyright notices and this permission notice appear in
  12.  * all copies of the software and related documentation, and (ii) the names of
  13.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  14.  * publicity relating to the software without the specific, prior written
  15.  * permission of Sam Leffler and Silicon Graphics.
  16.  * 
  17.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  18.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  19.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  20.  * 
  21.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  22.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  23.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  24.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  25.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  26.  * OF THIS SOFTWARE.
  27.  */
  28.  
  29. /*
  30.  * TIFF Library.
  31.  * Rev 5.0 Lempel-Ziv & Welch Compression Support
  32.  *
  33.  * This code is derived from the compress program whose code is
  34.  * derived from software contributed to Berkeley by James A. Woods,
  35.  * derived from original work by Spencer Thomas and Joseph Orost.
  36.  *
  37.  * The original Berkeley copyright notice appears below in its entirety.
  38.  */
  39. #include "tiffioP.h"
  40. #include <stdio.h>
  41. #include <assert.h>
  42. #include "prototypes.h"
  43.  
  44. #define MAXCODE(n)    ((1 << (n)) - 1)
  45. /*
  46.  * The TIFF spec specifies that encoded bit strings range
  47.  * from 9 to 12 bits.  This is somewhat unfortunate in that
  48.  * experience indicates full color RGB pictures often need
  49.  * ~14 bits for reasonable compression.
  50.  */
  51. #define    BITS_MIN    9        /* start with 9 bits */
  52. #define    BITS_MAX    12        /* max of 12 bit strings */
  53. /* predefined codes */
  54. #define    CODE_CLEAR    256        /* code to clear string table */
  55. #define    CODE_EOI    257        /* end-of-information code */
  56. #define CODE_FIRST    258        /* first free code entry */
  57. #define    CODE_MAX    MAXCODE(BITS_MAX)
  58. #ifdef notdef
  59. #define    HSIZE        9001        /* 91% occupancy */
  60. #define    HSHIFT        (8-(16-13))
  61. #else
  62. #define    HSIZE        5003        /* 80% occupancy */
  63. #define    HSHIFT        (8-(16-12))
  64. #endif
  65.  
  66. /*
  67.  * NB: The 5.0 spec describes a different algorithm than Aldus
  68.  *     implements.  Specifically, Aldus does code length transitions
  69.  *     one code earlier than should be done (for real LZW).
  70.  *     Earlier versions of this library implemented the correct
  71.  *     LZW algorithm, but emitted codes in a bit order opposite
  72.  *     to the TIFF spec.  Thus, to maintain compatibility w/ Aldus
  73.  *     we interpret MSB-LSB ordered codes to be images written w/
  74.  *     old versions of this library, but otherwise adhere to the
  75.  *     Aldus "off by one" algorithm.
  76.  *
  77.  * Future revisions to the TIFF spec are expected to "clarify this issue".
  78.  */
  79. #define    SetMaxCode(sp, v) {            \
  80.     (sp)->lzw_maxcode = (v)-1;        \
  81.     if ((sp)->lzw_flags & LZW_COMPAT)    \
  82.         (sp)->lzw_maxcode++;        \
  83. }
  84.  
  85. /*
  86.  * Decoding-specific state.
  87.  */
  88. struct decode {
  89.     short    prefixtab[HSIZE];    /* prefix(code) */
  90.     u_char    suffixtab[CODE_MAX+1];    /* suffix(code) */
  91.     u_char    stack[HSIZE-(CODE_MAX+1)];
  92.     u_char    *stackp;        /* stack pointer */
  93.     int    firstchar;        /* of string associated w/ last code */
  94. };
  95.  
  96. /*
  97.  * Encoding-specific state.
  98.  */
  99. struct encode {
  100.     long    checkpoint;        /* point at which to clear table */
  101. #define CHECK_GAP    10000        /* enc_ratio check interval */
  102.     long    ratio;            /* current compression ratio */
  103.     long    incount;        /* (input) data bytes encoded */
  104.     long    outcount;        /* encoded (output) bytes */
  105.     long    htab[HSIZE];        /* hash table */
  106.     short    codetab[HSIZE];        /* code table */
  107. };
  108.  
  109. #if USE_PROTOTYPES
  110. typedef    void (*predictorFunc)(char* data, int nbytes, int stride);
  111. #else
  112. typedef    void (*predictorFunc)();
  113. #endif
  114.  
  115. /*
  116.  * State block for each open TIFF
  117.  * file using LZW compression/decompression.
  118.  */
  119. typedef    struct {
  120.     int    lzw_oldcode;        /* last code encountered */
  121.     u_short    lzw_flags;
  122. #define    LZW_RESTART    0x01        /* restart interrupted decode */
  123. #define    LZW_COMPAT    0x02        /* read old bit-reversed codes */
  124.     u_short    lzw_nbits;        /* number of bits/code */
  125.     u_short    lzw_stride;        /* horizontal diferencing stride */
  126.     u_short    lzw_rowsize;        /* XXX maybe should be a long? */
  127.     predictorFunc lzw_hordiff;
  128.     int    lzw_maxcode;        /* maximum code for lzw_nbits */
  129.     long    lzw_bitoff;        /* bit offset into data */
  130.     long    lzw_bitsize;        /* size of strip in bits */
  131.     int    lzw_free_ent;        /* next free entry in hash table */
  132.     union {
  133.         struct    decode dec;
  134.         struct    encode enc;
  135.     } u;
  136. } LZWState;
  137. #define    dec_prefix    u.dec.prefixtab
  138. #define    dec_suffix    u.dec.suffixtab
  139. #define    dec_stack    u.dec.stack
  140. #define    dec_stackp    u.dec.stackp
  141. #define    dec_firstchar    u.dec.firstchar
  142.  
  143. #define    enc_checkpoint    u.enc.checkpoint
  144. #define    enc_ratio    u.enc.ratio
  145. #define    enc_incount    u.enc.incount
  146. #define    enc_outcount    u.enc.outcount
  147. #define    enc_htab    u.enc.htab
  148. #define    enc_codetab    u.enc.codetab
  149.  
  150. /* masks for extracting/inserting variable length bit codes */
  151. static const u_char rmask[9] =
  152.     { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  153. static const u_char lmask[9] =
  154.     { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  155.  
  156. #if USE_PROTOTYPES
  157. static    int LZWPreEncode(TIFF*);
  158. static    int LZWEncode(TIFF*, u_char*, int, u_int);
  159. static    int LZWEncodePredRow(TIFF*, u_char*, int, u_int);
  160. static    int LZWEncodePredTile(TIFF*, u_char*, int, u_int);
  161. static    int LZWPostEncode(TIFF*);
  162. static    int LZWDecode(TIFF*, u_char*, int, u_int);
  163. static    int LZWDecodePredRow(TIFF*, u_char*, int, u_int);
  164. static    int LZWDecodePredTile(TIFF*, u_char*, int, u_int);
  165. static    int LZWPreDecode(TIFF*);
  166. static    int LZWCleanup(TIFF*);
  167. static    int GetNextCode(TIFF*);
  168. static    void PutNextCode(TIFF*, int);
  169. static    void cl_block(TIFF*);
  170. static    void cl_hash(LZWState*);
  171. extern    int TIFFFlushData1(TIFF *);
  172. #else
  173. static    int LZWPreEncode(), LZWEncode(), LZWPostEncode();
  174. static    int LZWEncodePredRow(), LZWEncodePredTile();
  175. static    int LZWPreDecode(), LZWDecode();
  176. static    int LZWDecodePredRow(), LZWDecodePredTile();
  177. static    int LZWCleanup();
  178. static    int GetNextCode();
  179. static    void PutNextCode();
  180. static    void cl_block();
  181. static    void cl_hash();
  182. extern    int TIFFFlushData1();
  183. #endif
  184.  
  185. TIFFInitLZW(tif)
  186.     TIFF *tif;
  187. {
  188.     tif->tif_predecode = LZWPreDecode;
  189.     tif->tif_decoderow = LZWDecode;
  190.     tif->tif_decodestrip = LZWDecode;
  191.     tif->tif_decodetile = LZWDecode;
  192.     tif->tif_preencode = LZWPreEncode;
  193.     tif->tif_postencode = LZWPostEncode;
  194.     tif->tif_encoderow = LZWEncode;
  195.     tif->tif_encodestrip = LZWEncode;
  196.     tif->tif_encodetile = LZWEncode;
  197.     tif->tif_cleanup = LZWCleanup;
  198.     return (1);
  199. }
  200.  
  201. static
  202. DECLARE4(LZWCheckPredictor,
  203.     TIFF*, tif,
  204.     LZWState*, sp,
  205.     predictorFunc, pred8bit,
  206.     predictorFunc, pred16bit
  207. )
  208. {
  209.     TIFFDirectory *td = &tif->tif_dir;
  210.  
  211.     switch (td->td_predictor) {
  212.     case 1:
  213.         break;
  214.     case 2:
  215.         sp->lzw_stride = (td->td_planarconfig == PLANARCONFIG_CONTIG ?
  216.             td->td_samplesperpixel : 1);
  217.         switch (td->td_bitspersample) {
  218.         case 8:
  219.             sp->lzw_hordiff = pred8bit;
  220.             break;
  221.         case 16:
  222.             sp->lzw_hordiff = pred16bit;
  223.             break;
  224.         default:
  225.             TIFFError(tif->tif_name,
  226.     "Horizontal differencing \"Predictor\" not supported with %d-bit samples",
  227.                 td->td_bitspersample);
  228.             return (0);
  229.         }
  230.         break;
  231.     default:
  232.         TIFFError(tif->tif_name, "\"Predictor\" value %d not supported",
  233.             td->td_predictor);
  234.         return (0);
  235.     }
  236.     if (sp->lzw_hordiff) {
  237.         /*
  238.          * Calculate the scanline/tile-width size in bytes.
  239.          */
  240.         if (isTiled(tif))
  241.             sp->lzw_rowsize = TIFFTileRowSize(tif);
  242.         else
  243.             sp->lzw_rowsize = TIFFScanlineSize(tif);
  244.     }
  245.     return (1);
  246. }
  247.  
  248. /*
  249.  * LZW Decoder.
  250.  */
  251.  
  252. #define REPEAT4(n, op)        \
  253.     switch (n) {        \
  254.     default: { int i; for (i = n-4; i > 0; i--) { op; } } \
  255.     case 4:  op;        \
  256.     case 3:  op;        \
  257.     case 2:  op;        \
  258.     case 1:  op;        \
  259.     case 0:  ;            \
  260.     }
  261.  
  262. static void
  263. DECLARE3(horizontalAccumulate8,
  264.     register char*, cp,
  265.     register int, cc,
  266.     register int, stride
  267. )
  268. {
  269.     if (cc > stride) {
  270.         cc -= stride;
  271.         do {
  272.             REPEAT4(stride, cp[stride] += cp[0]; cp++)
  273.             cc -= stride;
  274.         } while (cc > 0);
  275.     }
  276. }
  277.  
  278. static void
  279. DECLARE3(horizontalAccumulate16,
  280.     char*, cp,
  281.     int, cc,
  282.     register int, stride
  283. )
  284. {
  285.     register short* wp = (short *)cp;
  286.     register int wc = cc / 2;
  287.  
  288.     if (wc > stride) {
  289.         wc -= stride;
  290.         do {
  291.             REPEAT4(stride, wp[stride] += wp[0]; wp++)
  292.             wc -= stride;
  293.         } while (wc > 0);
  294.     }
  295. }
  296.  
  297. /*
  298.  * Setup state for decoding a strip.
  299.  */
  300. static
  301. LZWPreDecode(tif)
  302.     TIFF *tif;
  303. {
  304.     register LZWState *sp = (LZWState *)tif->tif_data;
  305.     register int code;
  306.  
  307.     if (sp == NULL) {
  308.         tif->tif_data = malloc(sizeof (LZWState));
  309.         if (tif->tif_data == NULL) {
  310.             TIFFError("LZWPreDecode",
  311.                 "No space for LZW state block");
  312.             return (0);
  313.         }
  314.         sp = (LZWState *)tif->tif_data;
  315.         sp->lzw_flags = 0;
  316.         sp->lzw_hordiff = 0;
  317.         sp->lzw_rowsize = 0;
  318.         if (!LZWCheckPredictor(tif, sp,
  319.           horizontalAccumulate8, horizontalAccumulate16))
  320.             return (0);
  321.         if (sp->lzw_hordiff) {
  322.             /*
  323.              * Override default decoding method with
  324.              * one that does the predictor stuff.
  325.              */
  326.             tif->tif_decoderow = LZWDecodePredRow;
  327.             tif->tif_decodestrip = LZWDecodePredTile;
  328.             tif->tif_decodetile = LZWDecodePredTile;
  329.         }
  330.     } else
  331.         sp->lzw_flags &= ~LZW_RESTART;
  332.     sp->lzw_nbits = BITS_MIN;
  333.     /*
  334.      * Pre-load the table.
  335.      */
  336.     for (code = 255; code >= 0; code--)
  337.         sp->dec_suffix[code] = (u_char)code;
  338.     sp->lzw_free_ent = CODE_FIRST;
  339.     sp->lzw_bitoff = 0;
  340.     /* calculate data size in bits */
  341.     sp->lzw_bitsize = tif->tif_rawdatasize;
  342.     sp->lzw_bitsize = (sp->lzw_bitsize << 3) - (BITS_MAX-1);
  343.     sp->dec_stackp = sp->dec_stack;
  344.     sp->lzw_oldcode = -1;
  345.     sp->dec_firstchar = -1;
  346.     /*
  347.      * Check for old bit-reversed codes.  All the flag
  348.      * manipulations are to insure only one warning is
  349.      * given for a file.
  350.      */
  351.     if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) {
  352.         if ((sp->lzw_flags & LZW_COMPAT) == 0)
  353.             TIFFWarning(tif->tif_name,
  354.                 "Old-style LZW codes, convert file");
  355.         sp->lzw_flags |= LZW_COMPAT;
  356.     } else
  357.         sp->lzw_flags &= ~LZW_COMPAT;
  358.     SetMaxCode(sp, MAXCODE(BITS_MIN));
  359.     return (1);
  360. }
  361.  
  362. /*
  363.  * Decode a "hunk of data".
  364.  */
  365. static
  366. LZWDecode(tif, op0, occ0, s)
  367.     TIFF *tif;
  368.     u_char *op0;
  369.     u_int s;
  370. {
  371.     register char *op = (char *)op0;
  372.     register int occ = occ0;
  373.     register LZWState *sp = (LZWState *)tif->tif_data;
  374.     register int code;
  375.     register u_char *stackp;
  376.     int firstchar, oldcode, incode;
  377.  
  378.     stackp = sp->dec_stackp;
  379.     /*
  380.      * Restart interrupted unstacking operations.
  381.      */
  382.     if (sp->lzw_flags & LZW_RESTART) {
  383.         do {
  384.             if (--occ < 0) {    /* end of scanline */
  385.                 sp->dec_stackp = stackp;
  386.                 return (1);
  387.             }
  388.             *op++ = *--stackp;
  389.         } while (stackp > sp->dec_stack);
  390.         sp->lzw_flags &= ~LZW_RESTART;
  391.     }
  392.     oldcode = sp->lzw_oldcode;
  393.     firstchar = sp->dec_firstchar;
  394.     while (occ > 0 && (code = GetNextCode(tif)) != CODE_EOI) {
  395.         if (code == CODE_CLEAR) {
  396.             bzero(sp->dec_prefix, sizeof (sp->dec_prefix));
  397.             sp->lzw_free_ent = CODE_FIRST;
  398.             sp->lzw_nbits = BITS_MIN;
  399.             SetMaxCode(sp, MAXCODE(BITS_MIN));
  400.             if ((code = GetNextCode(tif)) == CODE_EOI)
  401.                 break;
  402.             *op++ = code, occ--;
  403.             oldcode = firstchar = code;
  404.             continue;
  405.         }
  406.         incode = code;
  407.         /*
  408.          * When a code is not in the table we use (as spec'd):
  409.          *    StringFromCode(oldcode) +
  410.          *        FirstChar(StringFromCode(oldcode))
  411.          */
  412.         if (code >= sp->lzw_free_ent) {    /* code not in table */
  413.             *stackp++ = firstchar;
  414.             code = oldcode;
  415.         }
  416.  
  417.         /*
  418.          * Generate output string (first in reverse).
  419.          */
  420.         for (; code >= 256; code = sp->dec_prefix[code])
  421.             *stackp++ = sp->dec_suffix[code];
  422.         *stackp++ = firstchar = sp->dec_suffix[code];
  423.         do {
  424.             if (--occ < 0) {    /* end of scanline */
  425.                 sp->lzw_flags |= LZW_RESTART;
  426.                 break;
  427.             }
  428.             *op++ = *--stackp;
  429.         } while (stackp > sp->dec_stack);
  430.  
  431.         /*
  432.          * Add the new entry to the code table.
  433.          */
  434.         if ((code = sp->lzw_free_ent) < CODE_MAX) {
  435.             sp->dec_prefix[code] = (u_short)oldcode;
  436.             sp->dec_suffix[code] = firstchar;
  437.             sp->lzw_free_ent++;
  438.             /*
  439.              * If the next entry is too big for the
  440.              * current code size, then increase the
  441.              * size up to the maximum possible.
  442.              */
  443.             if (sp->lzw_free_ent > sp->lzw_maxcode) {
  444.                 sp->lzw_nbits++;
  445.                 if (sp->lzw_nbits > BITS_MAX)
  446.                     sp->lzw_nbits = BITS_MAX;
  447.                 SetMaxCode(sp, MAXCODE(sp->lzw_nbits));
  448.             }
  449.         } 
  450.         oldcode = incode;
  451.     }
  452.     sp->dec_stackp = stackp;
  453.     sp->lzw_oldcode = oldcode;
  454.     sp->dec_firstchar = firstchar;
  455.     if (occ > 0) {
  456.         TIFFError(tif->tif_name,
  457.         "LZWDecode: Not enough data at scanline %d (short %d bytes)",
  458.             tif->tif_row, occ);
  459.         return (0);
  460.     }
  461.     return (1);
  462. }
  463.  
  464. /*
  465.  * Decode a scanline and apply the predictor routine.
  466.  */
  467. static
  468. LZWDecodePredRow(tif, op0, occ0, s)
  469.     TIFF *tif;
  470.     u_char *op0;
  471.     u_int s;
  472. {
  473.     LZWState *sp = (LZWState *)tif->tif_data;
  474.  
  475.     if (LZWDecode(tif, op0, occ0, s)) {
  476.         (*sp->lzw_hordiff)((char *)op0, occ0, sp->lzw_stride);
  477.         return (1);
  478.     } else
  479.         return (0);
  480. }
  481.  
  482. /*
  483.  * Decode a tile/strip and apply the predictor routine.
  484.  * Note that horizontal differencing must be done on a
  485.  * row-by-row basis.  The width of a "row" has already
  486.  * been calculated at pre-decode time according to the
  487.  * strip/tile dimensions.
  488.  */
  489. static
  490. LZWDecodePredTile(tif, op0, occ0, s)
  491.     TIFF *tif;
  492.     u_char *op0;
  493.     u_int s;
  494. {
  495.     LZWState *sp = (LZWState *)tif->tif_data;
  496.  
  497.     if (!LZWDecode(tif, op0, occ0, s))
  498.         return (0);
  499.     while (occ0 > 0) {
  500.         (*sp->lzw_hordiff)((char *)op0, sp->lzw_rowsize, sp->lzw_stride);
  501.         occ0 -= sp->lzw_rowsize;
  502.         op0 += sp->lzw_rowsize;
  503.     }
  504.     return (1);
  505. }
  506.  
  507. /*
  508.  * Get the next code from the raw data buffer.
  509.  */
  510. static
  511. GetNextCode(tif)
  512.     TIFF *tif;
  513. {
  514.     register LZWState *sp = (LZWState *)tif->tif_data;
  515.     register int code, bits;
  516.     register long r_off;
  517.     register u_char *bp;
  518.  
  519.     /*
  520.      * This check shouldn't be necessary because each
  521.      * strip is suppose to be terminated with CODE_EOI.
  522.      * At worst it's a substitute for the CODE_EOI that's
  523.      * supposed to be there (see calculation of lzw_bitsize
  524.      * in LZWPreDecode()).
  525.      */
  526.     if (sp->lzw_bitoff > sp->lzw_bitsize) {
  527.         TIFFWarning(tif->tif_name,
  528.             "LZWDecode: Strip %d not terminated with EOI code",
  529.             tif->tif_curstrip);
  530.         return (CODE_EOI);
  531.     }
  532.     r_off = sp->lzw_bitoff;
  533.     bits = sp->lzw_nbits;
  534.     /*
  535.      * Get to the first byte.
  536.      */
  537.     bp = (u_char *)tif->tif_rawdata + (r_off >> 3);
  538.     r_off &= 7;
  539.     if (sp->lzw_flags & LZW_COMPAT) {
  540.         /* Get first part (low order bits) */
  541.         code = (*bp++ >> r_off);
  542.         r_off = 8 - r_off;        /* now, offset into code word */
  543.         bits -= r_off;
  544.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  545.         if (bits >= 8) {
  546.             code |= *bp++ << r_off;
  547.             r_off += 8;
  548.             bits -= 8;
  549.         }
  550.         /* high order bits. */
  551.         code |= (*bp & rmask[bits]) << r_off;
  552.     } else {
  553.         r_off = 8 - r_off;        /* convert offset to count */
  554.         code = *bp++ & rmask[r_off];    /* high order bits */
  555.         bits -= r_off;
  556.         if (bits >= 8) {
  557.             code = (code<<8) | *bp++;
  558.             bits -= 8;
  559.         }
  560.         /* low order bits */
  561.         code = (code << bits) |
  562.             (((unsigned)(*bp & lmask[bits])) >> (8 - bits));
  563.     }
  564.     sp->lzw_bitoff += sp->lzw_nbits;
  565.     return (code);
  566. }
  567.  
  568. /*
  569.  * LZW Encoding.
  570.  */
  571.  
  572. static void
  573. DECLARE3(horizontalDifference8,
  574.     register char*, cp,
  575.     register int, cc,
  576.     register int, stride
  577. )
  578. {
  579.     if (cc > stride) {
  580.         cc -= stride;
  581.         cp += cc - 1;
  582.         do {
  583.             REPEAT4(stride, cp[stride] -= cp[0]; cp--)
  584.             cc -= stride;
  585.         } while (cc > 0);
  586.     }
  587. }
  588.  
  589. static void
  590. DECLARE3(horizontalDifference16,
  591.     char*, cp,
  592.     int, cc,
  593.     register int, stride
  594. )
  595. {
  596.     register short *wp = (short *)cp;
  597.     register int wc = cc/2;
  598.  
  599.     if (wc > stride) {
  600.         wc -= stride;
  601.         wp += wc - 1;
  602.         do {
  603.             REPEAT4(stride, wp[stride] -= wp[0]; wp--)
  604.             wc -= stride;
  605.         } while (wc > 0);
  606.     }
  607. }
  608.  
  609. /*
  610.  * Reset encoding state at the start of a strip.
  611.  */
  612. static
  613. LZWPreEncode(tif)
  614.     TIFF *tif;
  615. {
  616.     register LZWState *sp = (LZWState *)tif->tif_data;
  617.  
  618.     if (sp == NULL) {
  619.         tif->tif_data = malloc(sizeof (LZWState));
  620.         if (tif->tif_data == NULL) {
  621.             TIFFError("LZWPreEncode",
  622.                 "No space for LZW state block");
  623.             return (0);
  624.         }
  625.         sp = (LZWState *)tif->tif_data;
  626.         sp->lzw_flags = 0;
  627.         sp->lzw_hordiff = 0;
  628.         if (!LZWCheckPredictor(tif, sp,
  629.             horizontalDifference8, horizontalDifference16))
  630.             return (0);
  631.         if (sp->lzw_hordiff) {
  632.             tif->tif_encoderow = LZWEncodePredRow;
  633.             tif->tif_encodestrip = LZWEncodePredTile;
  634.             tif->tif_encodetile = LZWEncodePredTile;
  635.         }
  636.     }
  637.     sp->enc_checkpoint = CHECK_GAP;
  638.     SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
  639.     cl_hash(sp);        /* clear hash table */
  640.     sp->lzw_bitoff = 0;
  641.     sp->lzw_bitsize = (tif->tif_rawdatasize << 3) - (BITS_MAX-1);
  642.     sp->lzw_oldcode = -1;    /* generates CODE_CLEAR in LZWEncode */
  643.     return (1);
  644. }
  645.  
  646. /*
  647.  * Encode a scanline of pixels.
  648.  *
  649.  * Uses an open addressing double hashing (no chaining) on the 
  650.  * prefix code/next character combination.  We do a variant of
  651.  * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
  652.  * relatively-prime secondary probe.  Here, the modular division
  653.  * first probe is gives way to a faster exclusive-or manipulation. 
  654.  * Also do block compression with an adaptive reset, whereby the
  655.  * code table is cleared when the compression ratio decreases,
  656.  * but after the table fills.  The variable-length output codes
  657.  * are re-sized at this point, and a CODE_CLEAR is generated
  658.  * for the decoder. 
  659.  */
  660. static
  661. LZWEncode(tif, bp, cc, s)
  662.     TIFF *tif;
  663.     u_char *bp;
  664.     int cc;
  665.     u_int s;
  666. {
  667.     static char module[] = "LZWEncode";
  668.     register LZWState *sp;
  669.     register long fcode;
  670.     register int h, c, ent, disp;
  671.  
  672.     if ((sp = (LZWState *)tif->tif_data) == NULL)
  673.         return (0);
  674.     ent = sp->lzw_oldcode;
  675.     if (ent == -1 && cc > 0) {
  676.         PutNextCode(tif, CODE_CLEAR);
  677.         ent = *bp++; cc--; sp->enc_incount++;
  678.     }
  679.     while (cc > 0) {
  680.         c = *bp++; cc--; sp->enc_incount++;
  681.         fcode = ((long)c << BITS_MAX) + ent;
  682.         h = (c << HSHIFT) ^ ent;    /* xor hashing */
  683.         if (sp->enc_htab[h] == fcode) {
  684.             ent = sp->enc_codetab[h];
  685.             continue;
  686.         }
  687.         if (sp->enc_htab[h] >= 0) {
  688.             /*
  689.              * Primary hash failed, check secondary hash.
  690.              */
  691.             disp = HSIZE - h;
  692.             if (h == 0)
  693.                 disp = 1;
  694.             do {
  695.                 if ((h -= disp) < 0)
  696.                     h += HSIZE;
  697.                 if (sp->enc_htab[h] == fcode) {
  698.                     ent = sp->enc_codetab[h];
  699.                     goto hit;
  700.                 }
  701.             } while (sp->enc_htab[h] >= 0);
  702.         }
  703.         /*
  704.          * New entry, emit code and add to table.
  705.          */
  706.         PutNextCode(tif, ent);
  707.         ent = c;
  708.         sp->enc_codetab[h] = sp->lzw_free_ent++;
  709.         sp->enc_htab[h] = fcode;
  710.         if (sp->lzw_free_ent == CODE_MAX-1) {
  711.             /* table is full, emit clear code and reset */
  712.             cl_hash(sp);
  713.             PutNextCode(tif, CODE_CLEAR);
  714.             SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
  715.         } else {
  716.             /*
  717.              * If the next entry is going to be too big for
  718.              * the code size, then increase it, if possible.
  719.              */
  720.             if (sp->lzw_free_ent > sp->lzw_maxcode) {
  721.                 sp->lzw_nbits++;
  722.                 assert(sp->lzw_nbits <= BITS_MAX);
  723.                 SetMaxCode(sp, MAXCODE(sp->lzw_nbits)+1);
  724.             } else if (sp->enc_incount >= sp->enc_checkpoint)
  725.                 cl_block(tif);
  726.         }
  727.     hit:
  728.         ;
  729.     }
  730.     sp->lzw_oldcode = ent;
  731.     return (1);
  732. }
  733.  
  734. static
  735. LZWEncodePredRow(tif, bp, cc, s)
  736.     TIFF *tif;
  737.     u_char *bp;
  738.     int cc;
  739.     u_int s;
  740. {
  741.     LZWState *sp = (LZWState *)tif->tif_data;
  742.  
  743. /* XXX horizontal differencing alters user's data XXX */
  744.     (*sp->lzw_hordiff)((char *)bp, cc, sp->lzw_stride);
  745.     return (LZWEncode(tif, bp, cc, s));
  746. }
  747.  
  748. static
  749. LZWEncodePredTile(tif, bp0, cc0, s)
  750.     TIFF *tif;
  751.     u_char *bp0;
  752.     int cc0;
  753.     u_int s;
  754. {
  755.     LZWState *sp = (LZWState *)tif->tif_data;
  756.     int cc = cc0;
  757.     u_char *bp = bp0;
  758.  
  759.     while (cc > 0) {
  760.         (*sp->lzw_hordiff)((char *)bp, sp->lzw_rowsize, sp->lzw_stride);
  761.         cc -= sp->lzw_rowsize;
  762.         bp += sp->lzw_rowsize;
  763.     }
  764.     return (LZWEncode(tif, bp0, cc0, s));
  765. }
  766.  
  767. /*
  768.  * Finish off an encoded strip by flushing the last
  769.  * string and tacking on an End Of Information code.
  770.  */
  771. static
  772. LZWPostEncode(tif)
  773.     TIFF *tif;
  774. {
  775.     LZWState *sp = (LZWState *)tif->tif_data;
  776.  
  777.     if (sp->lzw_oldcode != -1) {
  778.         PutNextCode(tif, sp->lzw_oldcode);
  779.         sp->lzw_oldcode = -1;
  780.     }
  781.     PutNextCode(tif, CODE_EOI);
  782.     return (1);
  783. }
  784.  
  785. static void
  786. PutNextCode(tif, c)
  787.     TIFF *tif;
  788.     int c;
  789. {
  790.     register LZWState *sp = (LZWState *)tif->tif_data;
  791.     register long r_off;
  792.     register int bits, code = c;
  793.     register char *bp;
  794.  
  795.     r_off = sp->lzw_bitoff;
  796.     bits = sp->lzw_nbits;
  797.     /*
  798.      * Flush buffer if code doesn't fit.
  799.      */
  800.     if (r_off + bits > sp->lzw_bitsize) {
  801.         /*
  802.          * Calculate the number of full bytes that can be
  803.          * written and save anything else for the next write.
  804.          */
  805.         if (r_off & 7) {
  806.             tif->tif_rawcc = r_off >> 3;
  807.             bp = tif->tif_rawdata + tif->tif_rawcc;
  808.             (void) TIFFFlushData1(tif);
  809.             tif->tif_rawdata[0] = *bp;
  810.         } else {
  811.             /*
  812.              * Otherwise, on a byte boundary (in
  813.              * which tiff_rawcc is already correct).
  814.              */
  815.             (void) TIFFFlushData1(tif);
  816.         }
  817.         bp = tif->tif_rawdata;
  818.         sp->lzw_bitoff = (r_off &= 7);
  819.     } else {
  820.         /*
  821.          * Get to the first byte.
  822.          */
  823.         bp = tif->tif_rawdata + (r_off >> 3);
  824.         r_off &= 7;
  825.     }
  826.     /*
  827.      * Note that lzw_bitoff is maintained as the bit offset
  828.      * into the buffer w/ a right-to-left orientation (i.e.
  829.      * lsb-to-msb).  The bits, however, go in the file in
  830.      * an msb-to-lsb order.
  831.      */
  832.     bits -= (8 - r_off);
  833.     *bp = (*bp & lmask[r_off]) | (code >> bits);
  834.     bp++;
  835.     if (bits >= 8) {
  836.         bits -= 8;
  837.         *bp++ = code >> bits;
  838.     }
  839.     if (bits)
  840.         *bp = (code & rmask[bits]) << (8 - bits);
  841.     /*
  842.      * enc_outcount is used by the compression analysis machinery
  843.      * which resets the compression tables when the compression
  844.      * ratio goes up.  lzw_bitoff is used here (in PutNextCode) for
  845.      * inserting codes into the output buffer.  tif_rawcc must
  846.      * be updated for the mainline write code in TIFFWriteScanline()
  847.      * so that data is flushed when the end of a strip is reached.
  848.      * Note that the latter is rounded up to ensure that a non-zero
  849.      * byte count is present. 
  850.      */
  851.     sp->enc_outcount += sp->lzw_nbits;
  852.     sp->lzw_bitoff += sp->lzw_nbits;
  853.     tif->tif_rawcc = (sp->lzw_bitoff + 7) >> 3;
  854. }
  855.  
  856. /*
  857.  * Check compression ratio and, if things seem to
  858.  * be slipping, clear the hash table and reset state.
  859.  */
  860. static void
  861. cl_block(tif)
  862.     TIFF *tif;
  863. {
  864.     register LZWState *sp = (LZWState *)tif->tif_data;
  865.     register long rat;
  866.  
  867.     sp->enc_checkpoint = sp->enc_incount + CHECK_GAP;
  868.     if (sp->enc_incount > 0x007fffff) {    /* shift will overflow */
  869.         rat = sp->enc_outcount >> 8;
  870.         rat = (rat == 0 ? 0x7fffffff : sp->enc_incount / rat);
  871.     } else
  872.         rat = (sp->enc_incount<<8)/sp->enc_outcount; /* 8 fract bits */
  873.     if (rat <= sp->enc_ratio) {
  874.         cl_hash(sp);
  875.         PutNextCode(tif, CODE_CLEAR);
  876.         SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
  877.     } else
  878.         sp->enc_ratio = rat;
  879. }
  880.  
  881. /*
  882.  * Reset code table and related statistics.
  883.  */
  884. static void
  885. cl_hash(sp)
  886.     LZWState *sp;
  887. {
  888.     register long *htab_p = sp->enc_htab+HSIZE;
  889.     register long i, m1 = -1;
  890.  
  891.     i = HSIZE - 16;
  892.      do {
  893.         *(htab_p-16) = m1;
  894.         *(htab_p-15) = m1;
  895.         *(htab_p-14) = m1;
  896.         *(htab_p-13) = m1;
  897.         *(htab_p-12) = m1;
  898.         *(htab_p-11) = m1;
  899.         *(htab_p-10) = m1;
  900.         *(htab_p-9) = m1;
  901.         *(htab_p-8) = m1;
  902.         *(htab_p-7) = m1;
  903.         *(htab_p-6) = m1;
  904.         *(htab_p-5) = m1;
  905.         *(htab_p-4) = m1;
  906.         *(htab_p-3) = m1;
  907.         *(htab_p-2) = m1;
  908.         *(htab_p-1) = m1;
  909.         htab_p -= 16;
  910.     } while ((i -= 16) >= 0);
  911.         for (i += 16; i > 0; i--)
  912.         *--htab_p = m1;
  913.  
  914.     sp->enc_ratio = 0;
  915.     sp->enc_incount = 0;
  916.     sp->enc_outcount = 0;
  917.     sp->lzw_free_ent = CODE_FIRST;
  918. }
  919.  
  920. static
  921. LZWCleanup(tif)
  922.     TIFF *tif;
  923. {
  924.     if (tif->tif_data) {
  925.         free(tif->tif_data);
  926.         tif->tif_data = NULL;
  927.     }
  928. }
  929.  
  930. /*
  931.  * Copyright (c) 1985, 1986 The Regents of the University of California.
  932.  * All rights reserved.
  933.  *
  934.  * This code is derived from software contributed to Berkeley by
  935.  * James A. Woods, derived from original work by Spencer Thomas
  936.  * and Joseph Orost.
  937.  *
  938.  * Redistribution and use in source and binary forms are permitted
  939.  * provided that the above copyright notice and this paragraph are
  940.  * duplicated in all such forms and that any documentation,
  941.  * advertising materials, and other materials related to such
  942.  * distribution and use acknowledge that the software was developed
  943.  * by the University of California, Berkeley.  The name of the
  944.  * University may not be used to endorse or promote products derived
  945.  * from this software without specific prior written permission.
  946.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  947.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  948.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  949.  */
  950.